package com.midea.leetcode;

import java.util.ArrayList;
import java.util.List;

public class LeetCode22 {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }

    public static List<String> generateParenthesis(int n) {
        char[] p = new char[]{'(', ')'};
        int[] pb = new int[]{n, n};
        List<String> result = new ArrayList<>();
        dfs2(p, pb, new StringBuffer(), result);
        return result;
    }

    /*static void dfs(char[] p, int[] pb, StringBuffer res, List<String> result) {
        //截止条件
        if (pb[0] == 0 && pb[1] == 0) {
            if (!result.contains(res.toString())) {
                result.add(res.toString());
            }
            return;
        }
        for (int i = 0; i < p.length; i++) {
            if (pb[i] > 0) {
                if (pb[0] == pb[1]) {
                    res.append(p[0]);
                    pb[0]--;
                    dfs(p, pb, res, result);
                    res.deleteCharAt(res.length() - 1);
                    pb[0]++;
                } else {
                    res.append(p[i]);
                    pb[i]--;
                    dfs(p, pb, res, result);
                    res.deleteCharAt(res.length() - 1);
                    pb[i]++;
                }
            }
        }
    }*/

    //第二种解法
    static void dfs2(char[] p, int[] pb, StringBuffer res, List<String> result) {
        //截止条件
        if (pb[0] == 0 && pb[1] == 0) {
            result.add(res.toString());
            return;
        }
        if (pb[0] > 0) {
            res.append(p[0]);
            pb[0]--;
            dfs2(p, pb, res, result);
            res.deleteCharAt(res.length() - 1);
            pb[0]++;
        }
        if (pb[1] > 0 && pb[0] != pb[1]) {
            res.append(p[1]);
            pb[1]--;
            dfs2(p, pb, res, result);
            res.deleteCharAt(res.length() - 1);
            pb[1]++;
        }
    }

}
